package leetcode_301_400;

import java.rmi.MarshalledObject;
import java.util.*;

public class LeeCode_316_failed {
    public static void main(String[] args) {
        System.out.println(removeDuplicateLetters("cbacdcbc"));
        System.out.println(removeDuplicateLetters("bcabc"));
        System.out.println(removeDuplicateLetters("cdadabcc"));
        System.out.println(removeDuplicateLetters("ecbacba"));
        System.out.println(removeDuplicateLetters("baabc"));
    }
    private static String removeDuplicateLetters(String s) {
        Set<Character> tmp = new HashSet<>();
        Set<Character> again = new HashSet<>();
        Map<Character, Integer> lasts = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (tmp.contains(c)){
                again.add(c);
                lasts.put(c, i);
            }
            tmp.add(c);
        }
        Set<Character> used = new HashSet<>();
        StringBuilder sb = new StringBuilder();
        int i = 0;
        while (i < s.length()){
            if (!again.contains(s.charAt(i))){
                sb.append(s.charAt(i));
                i++;
            }else {
                TreeMap<Character, Integer> setMap = new TreeMap<>();
                while (i < s.length() && again.contains(s.charAt(i))){
                    if (setMap.containsKey(s.charAt(i))){
                        i++;
                        continue;
                    }
                    if (!used.contains(s.charAt(i))){
                        setMap.put(s.charAt(i), i);
                    }
                    i++;
                }
                if (i < s.length()){
                    setMap.put(s.charAt(i), i);
                    Map.Entry<Character, Integer> firstEntry = setMap.pollFirstEntry();
                    char first = firstEntry.getKey();
                    i = firstEntry.getValue();
                    while (!setMap.isEmpty()){
                        Map.Entry<Character, Integer> entry = setMap.pollFirstEntry();
                        if (lasts.containsKey(entry.getKey()) && lasts.get(entry.getKey()) < i){
                            sb.append(entry.getKey());
                            used.add(entry.getKey());
                        }
                    }
                    sb.append(first);
                    used.add(first);
                    i++;
                }else {
                    if (setMap.isEmpty()){
                        break;
                    }
                    Map.Entry<Character, Integer> firstEntry = setMap.pollFirstEntry();
                    char first = firstEntry.getKey();
                    i = firstEntry.getValue();
                    while (!setMap.isEmpty()) {
                        Map.Entry<Character, Integer> entry = setMap.pollFirstEntry();
                        if (lasts.get(entry.getKey()) < i){
                            sb.append(entry.getKey());
                            used.add(entry.getKey());
                        }
                    }
                    sb.append(first);
                    used.add(first);
                    i++;
                }
            }
        }
        return sb.toString();
    }
}
